package org.ala.tree.lsm.tools;

/**
 * 布隆过滤器
 * <p>	想不通为啥被炒的这么热，能解决的场景实在有限
 * <p>	实际存储的bitmap简化为long数组，所以最大容量 = 2^31-1 * 64
 *
 * @author ala
 * @date 2025年5月23日
 */
public class BloomFilter {
	/**
	 * 	(log2)²
	 */
	public static final double LOG2_POW2 = Math.log(2) * Math.log(2);
	/**
	 * 	预计元素数量
	 */
	protected int n;
	/**
	 * 	预计误判率（默认0.01，1%）
	 */
	protected double p;
	/**
	 * 每个子数组容量
	 */
	protected int c;
	/**
	 * hash函数
	 */
	protected IHash[] hashs;
	/**
	 * 每个hash函数对应的数组
	 */
	protected long[][] bitmaps;
	
	
	public BloomFilter() {
		super();
	}
	public BloomFilter(int n, double p) {
		this(n, p, new MurmurHash(1024), new MurmurHash(2048), new MurmurHash(4096));
	}
	public BloomFilter(int n, double p, IHash... hashs) {
		c = full64(calculateBitArraySize(n, p));
		
		this.hashs = hashs;
		bitmaps = new long[hashs.length][c / 64];
	}
	/**
	 * 	根据预估数量和误判率，计算每个子数组大小
	 */
	public static int calculateBitArraySize(int n, double p) {
		return (int) (-(n * Math.log(p)) / LOG2_POW2);
	}
	/**
	 * 	把n转换为>=n且64的倍数（因为实际是用long数组在存）
	 */
	public static int full64(int n) {
//		return n + (n % 64);
		return (n & 0x7FFFFFC0) + 0x40;
	}
	
	
	/**
	 * 	追加
	 */
	public boolean add(String key) {
		boolean r = false;
		for (int h = 0 ; h < hashs.length ; h++) {
			int hash = Math.abs(hashs[h].hash(key) % c);
			int i = hash >>> 6, j = hash & 0x3f;
			boolean b = (bitmaps[h][i] & 1l << j) == 0;
			if (b) {r = true;}
			bitmaps[h][i] |= 1l << j;
		}
		return r;
	}
	/**
	 * 	验证
	 */
	public boolean exists(String key) {
		for (int h = 0 ; h < hashs.length ; h++) {
			int hash = Math.abs(hashs[h].hash(key) % c);
			int i = hash >>> 6, j = hash & 0x3f;
			if ((bitmaps[h][i] & (1l << j)) == 0) {return false;}
		}
		return true;
	}
	

	/**
	 * 	hash
	 */
	public static interface IHash {
		int hash(String key);
	}
	public static class MurmurHash implements IHash {
		int seed;
		public MurmurHash() {
			super();
		}
		public MurmurHash(int seed) {this.seed = seed;}
		public int hash(String key) {
			final int prime = 0x9E3779B9; // 黄金分割比例的近似值
	        int hash = seed;
	        int length = key.length();
	 
	        char[] cs = key.toCharArray();
	        for (int i = 0; i < length; i++) {
	            char c = cs[i];
	            hash ^= c;
	            hash *= prime;
	            hash = (hash ^ (hash >>> 16)) * 0x85EBCA6B;
	            hash = (hash ^ (hash >>> 13)) * 0xC2B2AE35;
	        }
	 
	        hash ^= length;
	        hash = hash ^ (hash >>> 16);
	        return hash;
		}
	}
}
